Slowest Decryption Solver Script

code:python

import json

MOD = 69366296890289401502186466714324091327187023250181223675242511147337714372850256205482719088016822121023725770514726086328879208694006471882354415627744263559950687914692211431491359503896279403796581365981225023065749656346527652480289235008956593933928571457700779656030733229310882472880060831832351425517

def decrypt(c):

N = len(c)

memo = 0 * N

memo0 = N * (N - 1) // 2 * c0 % MOD

for k in range(N - 1, 0, -1):

over = sum(memoi for i in range(0, N, k))

tmp = sum(ci for i in range(0, N, k)) * pow((N + k - 1) // k, N - 1, MOD) * N * (N - 1) // 2 % MOD

memok = (tmp - over) % MOD

return sum(i * memoi for i in range(N)) % MOD

with open("encrypted.json") as f:

encrypted = json.load(f)

flag = decrypt(encrypted)

print(flag.to_bytes((flag.bit_length() + 7) // 8, byteorder="big"))

これは$ O(N\log N)時間で動きます。(実際、フラグを出力するまで1秒かかりません。)

This runs in $ O(N\log N)time. (in fact, this program outputs flag within 1 sec.)